// 可被3整除的最大和
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        const int N = 0x3f3f3f3f;
        int sum = 0, x1 = N, x2 = N, y1 = N, y2 = N;
        for (auto e : nums)
        {
            sum += e;
            if (e % 3 == 1)
            {
                if (e < x1) x2 = x1, x1 = e;
                else if (e < x2) x2 = e;
            }
            else if (e % 3 == 2)
            {
                if (e < y1) y2 = y1, y1 = e;
                else if (e < y2) y2 = e;
            }
        }
        if (sum % 3 == 1) return max(sum - x1, sum - y1 - y2);
        else if (sum % 3 == 2) return max(sum - y1, sum - x1 - x2);
        else return sum;
    }
};
    
// 重构字符串
class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> hash;
        char maxChar = 0;
        int maxCount = 0, n = s.size();
        // 1.统计所有字符出现的个数以及出现次数最多的字符
        for (auto e : s)
        {
            if (++hash[e] > maxCount)
            {
                maxCount = hash[e];
                maxChar = e;
            }
        }
        if (maxCount > (n + 1) / 2) return "";
        // 2.先处理出现次数最多的字符
        string str(n, ' ');
        int index = 0;
        for (int i = 0; i < maxCount; i++)
        {
            str[index] = maxChar;
            index += 2;
        }
        hash.erase(maxChar);
        // 3.再处理剩下的字符
        for (auto& [a, b] : hash)
        {
            for (int i = 0; i < b; i++)
            {
                if (index >= n) index = 1;
                str[index] = a;
                index += 2;
            }
        }
        return str;
    }
};
    
// 摆动序列
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;
        int ret = 0, left = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int right = nums[i + 1] - nums[i];// 计算接下来的趋势
            if (right == 0) continue;// 是否水平
            if (right * left <= 0) ret++;// 极大值或极小值
            left = right;// 更新趋势
        }
        return ret + 1; // 加上最后一个数
    }
};
    
// 最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > ret.back()) ret.push_back(nums[i]);
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = (left + right) >> 1;
                    if (ret[mid] < nums[i]) left = mid + 1;
                    else right = mid;
                }
                ret[left] = nums[i];
            }
        }
        return ret.size();
    }
};
    